//给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。 
//
// 
//
// 在杨辉三角中，每个数是它左上方和右上方的数的和。 
//
// 示例: 
//
// 输入: 3
//输出: [1,3,3,1]
// 
//
// 进阶： 
//
// 你可以优化你的算法到 O(k) 空间复杂度吗？ 
// Related Topics 数组 
// 👍 199 👎 0

package com.everyday.algorithm.changyf.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class PascalsTriangleIi {
    public static void main(String[] args) {
        Solution solution = new PascalsTriangleIi().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
      // list满足f(n) = f(n-1)*(index-n)/(n+1)
//    public List<Integer> getRow(int rowIndex) {
//        List<Integer> list = new ArrayList<Integer>(rowIndex + 1);
//        list.add(1);
//        if (rowIndex>0){
//            Long temp = 1L;
//            for (int i = 0; i < rowIndex/2; i++) {
//                temp = ((temp * (rowIndex-i)) / (i+1));
//                list.add(temp.intValue());
//            }
//            for (int j = (rowIndex-1)/2; j >= 0; j--) {
//                list.add(list.get(j));
//            }
//        }
//        return list;
//    }
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList<Integer>(rowIndex + 1);
        Long temp = 1L;
        for (int i = 0; i <= rowIndex; i++) {
            list.add(temp.intValue());
            temp = ((temp * (rowIndex-i))/(i+1));
        }
        return list;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}